package com.wtx.chapter03;

import java.util.Arrays;

/**
 * @description: 循环队列
 * @author: wtx
 * @createDate: 2020/5/17
 */
public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front;
    private int tail;
    private int size;

    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity+1]; //循环队列要浪费一个空间
        this.front=0;
        this.size=0;
        this.tail=0;
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }

    @Override
    public void enqueue(E e) {

        //队满，增容
        if( (tail+1)%data.length == front )
            resize( getCapacity()*2 );

        data[tail] = e;
        tail = (tail+1) % data.length;
        size++;
    }

    //扩容或者缩容
    private void resize( int newCapacity ){

        E[] newData = (E[]) new Object[newCapacity+1];

        for (int i = 0; i < size ; i++) {
            //注意，data的数据不一定从0号开始
            newData[i] = data[ (i+front)%data.length ];
            data = newData;
            front = 0;
            tail = size;
        }
    }

    @Override
    public int getSize() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return front==tail;
    }

    @Override
    public E dequeue() {
        if(isEmpty())
            throw new IllegalArgumentException("the queue is full");

        E ret = data[front];
        data[front] = null;
        front = (front+1) % data.length;
        size--;

        //缩容,并保证缩容后容量不为0
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0 )
            resize(getCapacity() / 2);

        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty())
            throw new IllegalArgumentException("the queue is empty");
        return data[front];
    }

    @Override
    public String toString() {
        return "LoopQueue{" +
                "data=" + Arrays.toString(data) +
                ", front=" + front +
                ", tail=" + tail +
                ", size=" + size +
                '}';
    }
}
